import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86131
 * Date: 2024-01-16
 * Time: 11:45
 */
public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {  //构造方法
            this.val = val;
        }
    }


    //以穷举的方法创建一棵二叉树
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;

    }

    //前序遍历
    void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);//递归
        preOrder(root.right);

    }
    public static int nodeSize;  //默认为0
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        nodeSize++;
        size(root.left);  //遍历左子树
        size(root.right);  //遍历右子树
        return nodeSize;
    }

    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        //左子树的个数加上右子树的结点个数加上根结点
        int tmp = size2(root.left)+size2(root.right)+1;
        return tmp;
    }

    //获取叶子结点个数
    public static int leafSize;
    public void getLeafNodeCount(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            //如果没有左右子树就说明是叶子节点
            leafSize++;
        }
        getLeafNodeCount(root.left);  //递归遍历左子树
        getLeafNodeCount(root.right);  //递归遍历右子树
    }

    public int getLeafNodeCount2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    //获取第K层结点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }else{
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }
    }

    //获取树的高度
    //整棵树的高度 = 左子树的高度和右子树的高度的最大值 + 1
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int hl = getHeight(root.left);  //获取左子树的高度
        int hr = getHeight(root.right);  //获取右子树的高度
        int max = hl>hr?hl:hr;
        return max+1;
    }

    //寻找树指定的元素
    public TreeNode find(TreeNode root,int val){
        if(root ==null){
            return null;
        }
        if(root.val == val){  //先判断根节点是不是我们要找的数据
            return root;
        }
        TreeNode leftVal = find(root.left,val);  //左子树去找
        if(leftVal != null){  //返回值不等于空说明找到了
            return leftVal;
        }
        TreeNode rightVal = find(root.right,val);  //右子树去找
        if(rightVal != null){  //返回值不等于空说明找到了
            return rightVal;
        }
        //左右都走完没找到返回空
        return null;
    }

    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){  //不为空就执行
            TreeNode cur = queue.poll();  //弹出队列元素
            System.out.print(cur.val+" ");
            if(cur.left != null){  //如果cur的左边不为空,就把它放进队列
                queue.offer(cur.left);
            }

            if(cur.right != null){  //如果cur的右边不为空,就把它放进队列
                queue.offer(cur.right);
            }
        }
    }

    //判断是不是完全二叉树
    public boolean add(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
           TreeNode cur = queue.poll();  //当队列不为空弹出一个元素给cur
           if(cur != null){    //cur不为空,不能结束
               queue.offer(cur.left);   //左右放入队列
               queue.offer(cur.right);
           }else{
               break;  //为空 结束,遍历队列剩下所有元素是不是null
           }
        }

        //遍历队列剩下所有元素,是不是都是null
         while(!queue.isEmpty()){
             TreeNode node = queue.poll();
             if(node != null){  //遍历队列里面的元素,出现不是空的说明不是完全二叉树
                 return false;
             }
         }
         return true;
    }


    //root 根节点
    //node  要查找指定的结点
    //stack 存储路径
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root== null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;   //根节点和指定的结点一样,说明找到了
        }
        boolean flgLeft = getPath(root.left,node,stack);  //找不到去左边找
        if(flgLeft){
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);  //找不到去右边找
        if(flgRight){
            return true;
        }

        stack.pop();//执行到这步说明没有找到,结点出栈
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode q,TreeNode p){
        if(root == null){
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        //调用函数,就可以知道p和q的路径
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        //接下来求它们的差值,所以就必须要知道它们的size
        int size1 = stack1.size();
        int size2 = stack2.size();

        if(size1 > size2){
            int size = size1-size2;
            while(size!= 0){
                stack1.pop();
                size--;
            }
        }else{
            int size = size2-size1;
            while(size!= 0){
                stack2.pop();
                size--;
            }
        }
        //同时出栈
        while(!stack1.isEmpty()&&!stack2.isEmpty()){
            if (stack1.peek().equals(stack2.peek())){  //先瞄一眼 确定值是否正确再弹出
                return stack1.pop();
            }else{
                stack2.pop();
                stack1.pop();
            }
        }
        return null;
    }

}
